package top.minuy.algorithm.sort.merge;
/**
 * @author Minuy
 * @time 10:20
 * @date 2021/8/28
 */
public class MergeSort {
    private MergeSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        Object[] temp = new Object[arr.length];
        sort(arr, 0, arr.length - 1,temp);
    }

    // 排序[l,r]
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r, Object[] temp) {
        if (l >= r) {
            return;
        }
        // int mid = (l + r) / 2;

        // 上面的写法可能导致l+r溢出
        int mid = l + (r-l) / 2;
        // [l,mid]
        sort(arr, l, mid,temp);
        // [mid+1,r]
        sort(arr, mid + 1, r,temp);

        // 优化1：两个有序数组，如果前一个数组的最大值小于等于后一个数组的最小值则不需要重新排序了
        if(arr[mid].compareTo(arr[mid+1])>0) {
            merge(arr, l, mid, r,temp);
        }
    }

    // [l,mid]  [mid+1,r]
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r,Object[] temp) {

        for (int i = l; i < r + 1; i++) {
            temp[i] = arr[i];
        }

        int IL = l, IR = mid + 1;


        // 范围是[l,r]
        for (int i = l; i < r + 1; i++) {
            if (IL > mid) {
                arr[i] = (E)temp[IR];
                IR++;
            } else if (IR > r) {
                arr[i] = (E)temp[IL];
                IL++;
            } else {
                if (((E)temp[IR]).compareTo(((E)temp[IL])) < 0) {
                    arr[i] = (E)temp[IR];
                    IR++;
                } else {
                    arr[i] = (E)temp[IL];
                    IL++;
                }
            }
        }
    }
}
